package pers.qianyu.month_202102.date_20210222;

import java.util.*;

/**
 * 460. LFU 缓存
 * https://leetcode-cn.com/problems/lfu-cache/
 *
 * @author mizzle rain
 * @date 2021年2月22日11:44:54
 */
public class LFUCache2 {
    private int cap, minFreq;
    private Map<Integer, Integer> keyFreqMap = new HashMap<>();
    private Map<Integer, Integer> keyValueMap = new HashMap<>();
    private Map<Integer, LinkedHashSet<Integer>> freqKeysMap = new HashMap<>();

    public LFUCache2(int capacity) {
        cap = capacity;
        minFreq = 0;
    }

    public int get(int key) {
        if (!keyValueMap.containsKey(key)) {
            return -1;
        }
        makeRecent(key);
        return keyValueMap.get(key);
    }

    public void put(int key, int value) {
        if (cap == 0) return;
        if (keyValueMap.containsKey(key)) {
            keyValueMap.put(key, value);
            makeRecent(key);
        } else {
            // 一定要提前删除，否则可能会出现，直接删除刚插入的元素的情况
            if (keyValueMap.size() == cap) {
                remove();
            }

            keyValueMap.put(key, value);
            keyFreqMap.put(key, 0);
            LinkedHashSet<Integer> set = freqKeysMap.getOrDefault(0, new LinkedHashSet<>());
            set.add(key);
            freqKeysMap.put(0, set);
            minFreq = 0;
        }
    }

    private void makeRecent(int key) {
        // 更新 freqKeysMap
        Integer freq = keyFreqMap.get(key);
        LinkedHashSet<Integer> set = freqKeysMap.get(freq);
        set.remove(key);
        if (set.isEmpty()) {
            freqKeysMap.remove(freq);
            if (minFreq == freq) minFreq++;
        }
        LinkedHashSet<Integer> newSet = freqKeysMap.getOrDefault(freq + 1, new LinkedHashSet<>());
        newSet.add(key);
        freqKeysMap.put(freq + 1, newSet);
        // 更新 keyFreqMap ： 频数 + 1
        keyFreqMap.put(key, freq + 1);
    }

    private void remove() {
        LinkedHashSet<Integer> set = freqKeysMap.get(minFreq);
        Integer key = set.iterator().next();
        set.remove(key);
        if (set.isEmpty()) {
            freqKeysMap.remove(minFreq);
            // 没必要更新 minFreq，因为 put 新元素之后 minFreq 又会被覆盖为 0
        }
        keyValueMap.remove(key);
        keyFreqMap.remove(key);
    }

    public static void main(String[] args) {
        LFUCache2 cache = new LFUCache2(0);
        cache.put(0, 0);
        System.out.println(cache.get(0));
    }

    //public static void main(String[] args) {
    //    // ["LFUCache","put","put","get","put","get","get","put","get","get","get"]
    //    //[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
    //    LFUCache cache = new LFUCache(2);
    //    cache.put(1, 1);
    //    cache.put(2, 2);
    //    System.out.println(cache.get(1));
    //    cache.put(3, 3);
    //    System.out.println(cache.get(2));
    //    System.out.println(cache.get(3));
    //    cache.put(4, 4);
    //    System.out.println(cache.get(1));
    //    System.out.println(cache.get(3));
    //    System.out.println(cache.get(4));
    //}
}